package solver;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

import model.Location;
import model.Machine;
import model.Problem;
import model.Process;
import model.Service;
import model.Solution;
import util.Chronograph;
import etm.core.configuration.EtmManager;
import etm.core.monitor.EtmMonitor;
import etm.core.monitor.EtmPoint;

// MathSolverLC is for Math Solver with Less Constraints
public class MathSolverGrbLC extends BaseSolver {
	private static final EtmMonitor etmMonitor = EtmManager.getEtmMonitor();
	private int numberOfSelectedProcesses;
	private int numberOfEligibleMachinesPerProcess;

	public MathSolverGrbLC(Problem problem, Solution initial_solution) {
		super(problem, initial_solution);
		numberOfSelectedProcesses = 10;
		numberOfEligibleMachinesPerProcess = 10;
	}

	public MathSolverGrbLC(Problem problem, Solution initial_solution,
			int numberOfSelectedProcesses,
			int numberOfEligibleMachinesPerProcess) {
		super(problem, initial_solution);
		this.numberOfSelectedProcesses = numberOfSelectedProcesses;
		this.numberOfEligibleMachinesPerProcess = numberOfEligibleMachinesPerProcess;
	}

	public MathSolverGrbLC(Problem problem, Solution initial_solution,
			Solution current_solution, int numberOfSelectedProcesses,
			int numberOfEligibleMachinesPerProcess) {
		super(problem, initial_solution, current_solution);
		this.numberOfSelectedProcesses = numberOfSelectedProcesses;
		this.numberOfEligibleMachinesPerProcess = numberOfEligibleMachinesPerProcess;
	}

	public void solve() {
		solve(100, false);
	}

	@Deprecated
	public void solve(int iterations, boolean saveLP) {
		GrbExtraLeanIPModelBuilder grbExtraLeanIPModelBuilder;
		setCurrentSolution(getInitialSolution().copy());
		getFullValidator().setSolutionPair(getInitialSolution(), getCurrentSolution());
		getFullValidator().computeCost();
		long best_cost = getFullValidator().getInitialSolutionCost();
		int improvement_counter = 0;
		for (int i = 0; i < iterations; i++) {
			System.out
					.printf("######################################  ROUND %d ######################################\n",
							i + 1);
			getFullValidator().printInitialSolutionCostAnalysis();
			getFullValidator().printNewSolutionCostAnalysis("CUR Solution");
			// List<Integer> selectedProcesses =
			// strategicallySelectProcessesAndMachines(
			// numberOfSelectedProcesses,
			// numberOfEligibleMachinesPerProcess);
			List<Integer> selectedProcesses = selectFullRandomProcessesAndMachines(
					numberOfSelectedProcesses,
					numberOfEligibleMachinesPerProcess);
			printEligibleMachinesPerProcess(selectedProcesses);

			grbExtraLeanIPModelBuilder = new GrbExtraLeanIPModelBuilder(
					getProblem(), selectedProcesses, true);
			grbExtraLeanIPModelBuilder.setInitialSolution(getInitialSolution());
			grbExtraLeanIPModelBuilder.setCurrentSolution(getCurrentSolution());


			boolean solved = grbExtraLeanIPModelBuilder.solve(saveLP);
			if (solved) {
				setPotentialSolution(grbExtraLeanIPModelBuilder
						.saveToSolution());
				getFullValidator().setSolutionPair(getInitialSolution(), getPotentialSolution());
				getFullValidator().computeCost();
				long potential_solution_cost = getFullValidator().getNewSolutionCost();
				if (potential_solution_cost < best_cost) {
					improvement_counter++;
					System.out
							.printf("Better solution found (round=%d, improvement=%d, number of moved processes=%d) %,d (reduced by %,d)\n",
									i + 1,
									improvement_counter,
									getNumberOfMovedProcesses(getPotentialSolution()),
									potential_solution_cost, best_cost
											- potential_solution_cost);
					getFullValidator().printNewSolutionCostAnalysis("POT Solution");
					if (getFullValidator().isFeasible()) {
						System.out.println(":)");
					} else {
						System.out.println("EXIT 1");
						System.out.println(":(");
						GrbExtraLeanIPModelBuidlerAnalyzer analyzer = new GrbExtraLeanIPModelBuidlerAnalyzer(
								getProblem(), getInitialSolution(), getPotentialSolution(),
								selectedProcesses);
						analyzer.analyze();
						return;
					}
					best_cost = potential_solution_cost;
					setCurrentSolution(getPotentialSolution().copy());
				} else {
					System.out
							.printf("No better solution found (round=%d, improvements=%d, number of moved processes=%d) was %,d  is %,d\n",
									i + 1,
									improvement_counter,
									getNumberOfMovedProcesses(getCurrentSolution()),
									best_cost, potential_solution_cost);
					getFullValidator().printNewSolutionCostAnalysis("POT Solution");
				}
				if (getFullValidator().isFeasible()) {
					System.out.println(":)");
				} else {
					System.out.println(":(");
					System.out.println("EXIT 2");
					GrbExtraLeanIPModelBuidlerAnalyzer analyzer = new GrbExtraLeanIPModelBuidlerAnalyzer(
							getProblem(), getInitialSolution(), getCurrentSolution(),
							selectedProcesses);
					analyzer.analyze();
					return;
				}
			} else {
				System.out.println("EXIT 3");
				GrbExtraLeanIPModelBuidlerAnalyzer analyzer = new GrbExtraLeanIPModelBuidlerAnalyzer(
						getProblem(), getInitialSolution(), getCurrentSolution(),
						selectedProcesses);
				analyzer.analyze();
				return;
			}
		}
	}

	public int solveWithTimeLimit(int seconds) {
		return solveWithTimeLimit(seconds, true);
	}

	public int solveWithTimeLimit(int seconds, boolean saveLP) {
		Chronograph chronos = new Chronograph();
		chronos.reset();
		int avg_round_time = 0;
		int round = 0;

		GrbExtraLeanIPModelBuilder grbExtraLeanIPModelBuilder;
		// current_solution = initial_solution.copy();
		getFullValidator().setSolutionPair(getInitialSolution(), getCurrentSolution());
		getFullValidator().computeCost();
		long best_cost = getFullValidator().getNewSolutionCost();
		int improvement_counter = 0;

		while (chronos.getElapsedTimeInSeconds() + avg_round_time < seconds) {
			if (Problem.VERBOSE) {
				System.out
						.printf("######################################  ROUND %d ######################################\n",
								round + 1);
				getFullValidator().printInitialSolutionCostAnalysis();
				getFullValidator().printNewSolutionCostAnalysis("CUR Solution");
			}
			List<Integer> selectedProcesses = selectFullRandomProcessesAndMachines(
					numberOfSelectedProcesses,
					numberOfEligibleMachinesPerProcess);

			// printEligibleMachinesPerProcess(selectedProcesses);
			long cutoff = computeCutOff(selectedProcesses);
			if (Problem.VERBOSE)
				System.out.printf("CUTOFF=%,d\n", cutoff);
			grbExtraLeanIPModelBuilder = new GrbExtraLeanIPModelBuilder(
					getProblem(), selectedProcesses, true, 5, cutoff);
			grbExtraLeanIPModelBuilder.setInitialSolution(getInitialSolution());
			grbExtraLeanIPModelBuilder.setCurrentSolution(getCurrentSolution());

			// grbExtraLeanIPModelBuilder
			// .includeConflictHardConstraints(includeConflictConstraints);
			// grbExtraLeanIPModelBuilder
			// .includeSpreadHardConstraints(includeSpreadConstraints);
			// grbExtraLeanIPModelBuilder
			// .includeDependencyHardConstraints(includeDependencyConstraints);
			// System.out
			// .printf("CONFLICT CONSTRAINTS=%s, SPREAD CONSTRAINTS=%s, DEPENDENCY CONSTRAINTS=%s\n",
			// includeConflictConstraints ? "INCLUDED"
			// : "NOT INCLUDED",
			// includeSpreadConstraints ? "INCLUDED"
			// : "NOT INCLUDED",
			// includeDependencyConstraints ? "INCLUDED"
			// : "NOT INCLUDED");

			boolean solved = grbExtraLeanIPModelBuilder.solve(saveLP);
			if (solved) {
				setPotentialSolution(grbExtraLeanIPModelBuilder
						.saveToSolution());

				getFullValidator().setSolutionPair(getInitialSolution(), getPotentialSolution());
				getFullValidator().computeCost();
				long potential_solution_cost = getFullValidator().getNewSolutionCost();
				if (potential_solution_cost < best_cost) {
					improvement_counter++;
					if (Problem.VERBOSE) {
						System.out
								.printf("Better solution found (round=%d, improvement=%d, number of moved processes=%d) %,d (reduced by %,d)\n",
										round + 1,
										improvement_counter,
										getNumberOfMovedProcesses(getPotentialSolution()),
										potential_solution_cost, best_cost
												- potential_solution_cost);
						getFullValidator().printNewSolutionCostAnalysis("POT Solution");
					}
					if (getFullValidator().isFeasible()) {
						if (Problem.VERBOSE)
							System.out.println(":)");
						best_cost = potential_solution_cost;
						setCurrentSolution(getPotentialSolution().copy());
					} else {
						if (Problem.VERBOSE) {
							System.out.println(":(");
						}
						GrbExtraLeanIPModelBuidlerAnalyzer analyzer = new GrbExtraLeanIPModelBuidlerAnalyzer(
								getProblem(), getInitialSolution(), getCurrentSolution(),
								selectedProcesses);
						analyzer.analyze();
						System.out.println("EXIT 1");
						return round + 1;
					}
				} else {
					if (Problem.VERBOSE) {
						System.out
								.printf("No better solution found (round=%d, improvements=%d, number of moved processes=%d) was %,d  is %,d\n",
										round + 1,
										improvement_counter,
										getNumberOfMovedProcesses(getCurrentSolution()),
										best_cost, potential_solution_cost);
						getFullValidator().printNewSolutionCostAnalysis("POT Solution");
					}
				}
			} else {
				// GrbExtraLeanIPModelBuidlerAnalyzer analyzer = new
				// GrbExtraLeanIPModelBuidlerAnalyzer(
				// problem, initial_solution, current_solution,
				// selectedProcesses);
				// analyzer.analyze();
				// System.out.println("EXIT 2");
				// return round + 1;
			}
			round++;
			avg_round_time = chronos.getElapsedTimeInSeconds() / round;
			chronos.lap();
		}
		return round;
	}

	private List<Integer> new_strategicallySelectProcessesAndMachines(int nop,
			int noem) {
		getProblem().clearEligibleMachines();
		nop = nop < getProblem().P ? nop : getProblem().P;
		noem = noem < getProblem().M ? noem : getProblem().M;
		List<Integer> selectedProcesses;
		selectedProcesses = randomlySelectProcesses(nop);

		// add all machines for each selected process
		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			for (int m_id = 0; m_id < getProblem().M; m_id++) {
				proc.addEligibleMachine(m_id);
			}
		}

		List<Integer> sameServiceProcesses = getProblem()
				.getProcessesFromSameService(selectedProcesses);
		selectedProcesses.removeAll(sameServiceProcesses);

		selectedProcesses.addAll(sameServiceProcesses);

		// keep |noem| machines at most for each selected process
		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			Collections.shuffle(proc.getEligibleMachines(), getRandom());
			int current_machine_id = getCurrentSolution()
					.getMachineIdForProcessId(p_id);
			boolean flag = false;
			while (proc.getEligibleMachines().size() > noem) {
				int m_id = proc.getEligibleMachines().get(0);
				if (m_id == current_machine_id)
					flag = true;
				proc.getEligibleMachines().remove(0);
			}
			if (flag)
				proc.addEligibleMachine(current_machine_id);
		}
		return selectedProcesses;
	}

	private List<Integer> strategicallySelectProcessesAndMachines(int nop,
			int noem) {
		getProblem().clearEligibleMachines();
		nop = nop < getProblem().P ? nop : getProblem().P;
		noem = noem < getProblem().M ? noem : getProblem().M;
		List<Integer> selectedProcesses;
		// selectedProcesses = randomlySelectOneProcessFromEachService(nop);
		selectedProcesses = randomlySelectProcesses(nop);

		// add all machines for each selected process
		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			for (int m_id = 0; m_id < getProblem().M; m_id++) {
				proc.addEligibleMachine(m_id);
			}
		}

			// keep |noem| machines at most for each selected process
		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			Collections.shuffle(proc.getEligibleMachines(), getRandom());
			int current_machine_id = getCurrentSolution()
					.getMachineIdForProcessId(p_id);
			boolean flag = false;
			while (proc.getEligibleMachines().size() > noem) {
				int m_id = proc.getEligibleMachines().get(0);
				if (m_id == current_machine_id)
					flag = true;
				proc.getEligibleMachines().remove(0);
			}
			if (flag)
				proc.addEligibleMachine(current_machine_id);
		}
		return selectedProcesses;
	}

	/**
	 * Randomly select one process from each one of nop (nop<=S) services
	 * 
	 * @param nop
	 * @return
	 */
	private List<Integer> randomlySelectOneProcessFromEachService(int nop) {
		if (nop > getProblem().S)
			nop = getProblem().S;
		List<Integer> selectedProcesses = new ArrayList<Integer>();
		List<Integer> ballot = new ArrayList<Integer>();
		for (int s_id = 0; s_id < getProblem().S; s_id++) {
			ballot.add(s_id);
		}
		Collections.shuffle(ballot, getRandom());
		for (int i = 0; i < nop; i++) {
			Service service = getProblem().getServices().get(ballot.get(i));
			int p_id = service.getRandomProcess(getRandom());
			selectedProcesses.add(p_id);
		}
		return selectedProcesses;
	}

	private List<Integer> randomlySelectProcesses(int nop) {
		if (nop > getProblem().P)
			nop = getProblem().P;
		List<Integer> selectedProcesses = new ArrayList<Integer>();
		List<Integer> ballot = new ArrayList<Integer>();
		for (int p_id = 0; p_id < getProblem().P; p_id++) {
			ballot.add(p_id);
		}
		Collections.shuffle(ballot, getRandom());
		for (int i = 0; i < nop; i++) {
			selectedProcesses.add(ballot.get(i));
		}
		return selectedProcesses;
	}

	public List<Integer> selectProcessesWithIntelligence(int nop, int noem) {
		EtmPoint point = etmMonitor
				.createPoint("MathSolverLC:selectProcessesWithIntelligence");
		getProblem().clearEligibleMachines();
		nop = nop < getProblem().P ? nop : getProblem().P;
		noem = noem < getProblem().M ? noem : getProblem().M;

		// 1) compute cost contribution of each machine
		getCurrentSolution().refreshLoadCostContribution();
		getCurrentSolution().refreshBalanceCostContribution();
		int[] m_a = new int[getProblem().M];
		long[] cc = new long[getProblem().M];
		int[] ev = new int[getProblem().M];
		for (int i = 0; i < getProblem().M; i++) {
			m_a[i] = i;
			cc[i] = getCurrentSolution().balance_cost_contribution_zipped[i]
					+ getCurrentSolution().load_cost_contribution_zipped[i];
			if (getCurrentSolution().balance_cost_contribution_zipped[i]
					+ getCurrentSolution().load_cost_contribution_zipped[i] == 0)
				ev[i]++;
		}
		sort(cc, m_a);
		// for (int i = 0; i < problem.M; i++)
		// System.out.printf("%,d m%d\n", cc[i], m_a[i]);

		// 2) select processes based on their contribution on most loaded
		// machines
		List<Integer> selectedProcesses = new ArrayList<Integer>();
		List<Integer> bannedProcesses = new ArrayList<Integer>();
		for (int i = 0; i < nop; i++) {
			int selected_process_id = -1;
			do {
				int roulette_selected_machine = roulette();
				selected_process_id = getCurrentSolution()
						.findMaxContributingProcess(roulette_selected_machine,
								bannedProcesses);
				System.out
						.printf("Selected machine: m%d order=%d cost=%,d Selected process=%d\n",
								m_a[roulette_selected_machine],
								roulette_selected_machine,
								cc[roulette_selected_machine],
								selected_process_id);
				if (selected_process_id == -1)
					System.out.println("TRY AGAIN!");
			} while (selected_process_id == -1);
			selectedProcesses.add(selected_process_id);
			// processes from the same service as selected_process_id should be
			// not selected (conflict constraint)
			int s_id = getProblem().getProcesses().get(selected_process_id)
					.getService();
			Service aService = getProblem().getServices().get(s_id);
			bannedProcesses.addAll(aService.getProcesses());
		}

		// 3) select machines for each process giving preference to machines
		// with larger sum of negative load cost values

		// add all machines for each selected process
		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			for (int m_id = 0; m_id < getProblem().M; m_id++) {
				proc.addEligibleMachine(m_id);
			}
		}
		filterMachinesSatisfyingConflictsConstraint(selectedProcesses);
		filterMachinesSatisfyingSpreadConstraints(selectedProcesses);

		for (Integer p_id : selectedProcesses) {
			Process proc = getProblem().getProcesses().get(p_id);
			long[] sum_negative_values = new long[proc.getEligibleMachines()
					.size()];
			int[] c_m_id = new int[proc.getEligibleMachines().size()];
			int i = 0;
			for (Integer m_id : proc.getEligibleMachines()) {
				sum_negative_values[i] = 0;
				c_m_id[i] = m_id;
				for (int r_id = 0; r_id < getProblem().RE; r_id++) {
					if (getCurrentSolution().load_cost_contribution_unzipped[m_id][r_id] < 0) {
						sum_negative_values[i] -= getCurrentSolution().load_cost_contribution_unzipped[m_id][r_id];
						getCurrentSolution().load_cost_contribution_unzipped[m_id][r_id] = 0;
					}
				}
				i++;
			}

			sort(sum_negative_values, c_m_id);
			int M = proc.getEligibleMachines().size();

			if (M < noem)
				noem = M;
			proc.clearEligibleMachines();
			int current_machine_id = getCurrentSolution()
					.getMachineIdForProcessId(p_id);
			proc.addEligibleMachine(current_machine_id);
			boolean[] selected = new boolean[M];
			for (int m = 0; m < M; m++) {
				if (c_m_id[m] == current_machine_id)
					selected[m] = true;
			}

			int k = 0;
			while (k < noem - 1) {
				int c = 0;
				for (int l = 0; l < M; l++) {
					if (selected[l] == false)
						c++;
				}
				int b = roulette(c);
				c = 0;
				for (int l = 0; l < M; l++) {
					if (selected[l] == false) {
						if (c == b) {
							selected[l] = true;
							proc.addEligibleMachine(c_m_id[l]);
							k++;
						}
						c++;
					}
				}
			}
		}

		point.collect();
		return selectedProcesses;
	}

	private int roulette() {
		return roulette(getProblem().M / 2);
	}

	private int roulette(int ro) {
		double sum = 0.0;
		for (int i = 1; i <= ro; i++) {
			sum += 1.0 / i;
		}
		double ball = getRandom().nextDouble();
		double x = 0.0;
		int i = 1;
		while (x < ball * sum) {
			x += 1.0 / i;
			i++;
		}
		return i - 1;
	}
}
